#include<iostream>
#include<string>
#include<vector>
#include<unordered_map>
using namespace std;

class Solution {
public:
    string modifyString(string s) {
        if (s.size() == 1) {
            if (s[0] == '?') s[0] = 'a';
            return s;
        }
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '?') {
                if (i == 0) {
                    for (int j = 0; j < 26; j++) {
                        if (j + 'a' != s[i + 1]) {
                            s[i] = j + 'a';
                        }
                    }
                }
                else if (i == s.size() - 1) {
                    for (int j = 0; j < 26; j++) {
                        if (j + 'a' != s[i - 1]) {
                            s[i] = j + 'a';
                        }
                    }
                }
                else {
                    for (int j = 0; j < 26; j++) {
                        if (j + 'a' != s[i - 1] && j + 'a' != s[i + 1]) {
                            s[i] = j + 'a';
                        }
                    }
                }
            }
        }
        return s;
    }
};

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int sum_time = 0;
        for (int i = 1; i < timeSeries.size(); i++) {
            if (timeSeries[i] - timeSeries[i - 1] >= duration) {
                sum_time += duration;
            }
            else {
                sum_time += timeSeries[i] - timeSeries[i - 1];
            }
        }
        sum_time += duration;
        return sum_time;
    }
};

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1)return s;
        string ans;
        vector<string> vstr;
        vstr.resize(numRows);
        int flag = 1;
        int i = 0;
        for (int j = 0; j < s.size(); j++) {
            if (i >= 0 && i < numRows) {
                vstr[i].push_back(s[j]);
                i += flag;
            }
            else if (i < 0) {
                i = 1;
                flag = 1;
                --j;
            }
            else if (i >= numRows) {
                i = numRows - 2;
                flag = -1;
                --j;
            }
        }
        for (int k = 0; k < vstr.size(); k++) {
            ans += vstr[k];
        }
        return ans;
    }
};


class Solution {
public:
    string countAndSay(int n) {
        string str1;
        str1.reserve(40);
        str1 += '1';
        string str2;
        while (--n) {
            if (str2.size() == 0) {
                char ch = str1[0];
                int digit = 0;
                for (int i = 0; i <= str1.size(); i++) {
                    if (i != str1.size() && ch == str1[i]) {
                        digit++;
                    }
                    else {
                        str2 += to_string(digit);
                        str2 += ch;
                        ch = str1[i];
                        digit = 1;
                    }
                }
                str1.clear();
            }
            else if (str1.size() == 0) {
                char ch = str2[0];
                int digit = 0;
                for (int i = 0; i <= str2.size(); i++) {
                    if (i != str2.size() && ch == str2[i]) {
                        digit++;
                    }
                    else {
                        str1 += to_string(digit);
                        str1 += ch;
                        ch = str2[i];
                        digit = 1;
                    }
                }
                str2.clear();
            }
        }
        return str1.size() == 0 ? str2 : str1;
    }
};

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        unordered_map<char, int> hash;
        int frog_d = 0;
        for (auto e : croakOfFrogs) {
            hash[e]++;
            if (e == 'c') {
                frog_d = max(frog_d, hash['c'] - hash['k']);
            }
            else if (hash['r'] > hash['c'] || hash['o'] > hash['r']
                || hash['a'] > hash['o'] || hash['k'] > hash['a']) {
                return -1;
            }
        }
        int tmp = hash['c'];
        for (auto& e : hash) {
            if (e.second != tmp) {
                return -1;
            }
        }
        return frog_d;
    }
};